/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author zhong
 *
 */
public class BagofTokens {
	public int bagOfTokensScore(int[] tokens, int P) {
		Arrays.sort(tokens);
		int n = tokens.length;
		int i = 0, j = n - 1;
		int power = P;
		int score = 0;

		int max = 0;
		boolean changed = true;
		while (changed) {
			changed = false;
			while (i < j && power >= tokens[i]) {
				power -= tokens[i];
				i++;
				score++;
				changed = true;
			}
			if (max < score) {
				max = score;
			}
			if (score != 0 && i < j) {
				score -= 1;
				power += tokens[j];
				j--;
				changed = true;
			}
		}
		if (i == j && power >= tokens[i]) {
			score++;
			if (max < score) {
				max = score;
			}
		}
		return max;
	}

	private boolean canContinue(TreeSet<Integer> tokenSet, int power, int score) {
		if (score != 0 && tokenSet.size() > 1) {
			return true;
		}
		if (!tokenSet.isEmpty() && power >= tokenSet.first()) {
			return true;
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] tokens = { 58, 91 };
		int P = 50;
		System.out.println(new BagofTokens().bagOfTokensScore(tokens, P));
	}

}
